package leetcode.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2023/11/12 23:38
 */
public class _207 {
    private boolean hasCycle;

    /**
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     * <p>
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
     * <p>
     * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] gragh = build(numCourses, prerequisites);
        boolean[] visted = new boolean[numCourses];
        boolean[] path = new boolean[numCourses];
        for (int i = 0; i < numCourses; i++) {
            track(gragh, i, visted, path);
        }
        return !hasCycle;
    }

    private void track(List<Integer>[] gragh, int i, boolean[] visted, boolean[] path) {

        if (path[i]) {
            hasCycle = true;
        }
        if (visted[i] || hasCycle) {
            return;
        }
        visted[i] = true;
        path[i] = true;
        for (Integer integer : gragh[i]) {
            track(gragh, integer, visted, path);
        }
        path[i] = false;
    }

    private List<Integer>[] build(int numCourses, int[][] prerequisites) {
        List<Integer>[] gragh = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            gragh[i] = new ArrayList<>();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int[] edge = prerequisites[i];
            int from = edge[1];
            int to = edge[0];
            gragh[from].add(to);
        }
        return gragh;
    }
}
